// 翻转 二叉树
// 方法 1 递归
var invertTree = function (root) {
  if (root === null) return null
  const left = invertTree(root.left)
  const right = invertTree(root.right)
  root.left = right
  root.right = left
  return root
}

// 方法 2 迭代 BFS
var invertTree = function (root) {
  if (root === null) return null
  let queue = [root]
  while (queue.length) {
    let node = queue.shift()
    let left = node.left
    let right = node.right
    node.left = right
    node.right = left
    if (node.left) {
      queue.push(node.left)
    }
    if (node.right) {
      queue.push(node.right)
    }
  }
  return root
}
// or DFS
var invertTree = function (root) {
  if (root === null) return null
  let queue = [root]
  while (queue.length) {
    let node = queue.pop()
    let left = node.left
    let right = node.right
    node.left = right
    node.right = left
    if (node.left) {
      queue.push(node.left)
    }
    if (node.right) {
      queue.push(node.right)
    }
  }
  return root
}
